4259. Минимум на стеке
Вам требуется
реализовать структуру данных, выполняющую следующие операции:
1.
Добавить элемент x
в конец структуры.
2.
Удалить последний элемент из структуры.
3.
Выдать минимальный элемент в структуре.
Вход. В первой строке задано количество операций n (1 ≤ n ≤ 106). Каждая из следующих n строк содержит одну операцию. В i-ой строке находится число ti
– тип операции:
·
1 если операция добавления;
·
2 если операция удаления;
·
3 если операция нахождения минимума;
В случае операции добавления после типа записано целое число x (-109 ≤ x ≤ 109) – элемент,
который следует добавить в структуру. Гарантируется, что перед каждой операцией
удаления или нахождения минимума структура не пуста.
Выход. Для каждой
операции нахождения минимума выведите в отдельной строке одно число –
минимальный элемент в структуре.
|
Пример
входа |
Пример
выхода |
|
8 1 2 1 3 1 -3 3 2 3 2 3 |
-3 2 2 |
РЕШЕНИЕ
стек
Анализ алгоритма
Очевидно, что
требуемой структурой данных является стек. Поскольку количество операций над
стеком n не больше 106, то
выберем в качестве его контейнера статический массив указанной длины.
Метод pop()
промоделируем как обычно удалением верхнего элемента стека, а метод push(x) перепишем следующим образом:
·
Если стек пуст, то занесем x в стек;
·
Иначе занесем в стек минимум среди x и текущего значения на его вершине.
Таким образом
минимальный элемент стека будет всегда находиться на его вершине. При этом сами
заносимые в стек значения мы теряем, хотя в действительности при дальнейших
запросах они и не нужны.
При занесении
числа 8 в структуру на вершину стека заносим min(8, 3) = 3.
Реализация алгоритма
Объявим класс Стек
и его методы.
class Stack {
public:
Stack(int
size);
void push(int x);
void pop();
int getMin();
private:
int* m;
int size;
};
Stack::Stack(int size = 1000001) {
m = new int[size];
this->size
= 0;
}
void Stack::push(int
x) {
if (size ==
0)
m[size++] = x;
else
{
int pos =
size - 1;
m[size++] = min(x,m[pos]);
}
}
void Stack::pop() {
size--;
}
int Stack::getMin() {
return
m[size-1];
}
Основная часть программы. Моделируем работу стека.
Stack s;
scanf("%d",&n);
while(n--)
{
scanf("%d",&op);
if (op == 1)
{
scanf("%d",&x);
s.push(x);
} else
if (op == 2)
{
s.pop();
} else
{
printf("%d\n",s.getMin());
}
}
Реализация Stack STL
Объявим рабочий стек.
stack<int> s;
Читаем количество операций n.
scanf("%d",&n);
while(n--)
{
Читаем тип операции op.
scanf("%d",&op);
if (op == 1)
{
Добавляем в стек число x.
scanf("%d",&x);
if
(s.empty())
s.push(x);
else
s.push(min(s.top(),x));
} else
if (op == 2)
{
Удаляем число из стека.
s.pop();
} else
{
Выводим минимум в структуре. Он лежит на вершине стека.
printf("%d\n",s.top());
}
}
Java реализация – Scannner
import java.util.*;
//import java.io.*;
public class Main
{
public static void
main(String[] args) // throws IOException
{
Scanner con = new
Scanner(System.in);
//Scanner
con = new Scanner(new FileReader ("4259.in"));
Stack<Integer> s = new
Stack<Integer>();
int n = con.nextInt();
while(n--
> 0)
{
int op = con.nextInt();
if (op ==
1)
{
int x = con.nextInt();
if (s.empty())
s.push(x);
else
s.push(Math.min(s.peek(),x));
} else
if (op ==
2)
{
s.pop();
} else
{
System.out.println(s.peek());
}
}
con.close();
}
}
Java реализация – Fast Scannner
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args) //throws IOException
{
//FastScanner con = new FastScanner(new FileReader
("4259.in"));
FastScanner con =
new FastScanner(new
InputStreamReader(System.in));
Stack<Integer> s = new Stack<Integer>();
int n = con.nextInt();
while(n-- > 0)
{
int op = con.nextInt();
if (op == 1)
{
int x = con.nextInt();
if (s.empty())
s.push(x);
else
s.push(Math.min(s.peek(),x));
} else
if (op == 2)
{
s.pop();
} else
{
System.out.println(s.peek());
}
}
}
}
class FastScanner
{
private BufferedReader br;
private StringTokenizer st;
public FastScanner(InputStreamReader
reader)
{
br = new BufferedReader(reader);
}
public String next()
{
while (st == null || !st.hasMoreTokens())
{
try
{
st = new StringTokenizer(br.readLine());
} catch (Exception e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return Integer.parseInt(next());
}
public double nextDouble()
{
return Double.parseDouble(next());
}
public void close() throws Exception
{
br.close();
}
}